package main

import "fmt"

// 双向链表结构
type TwoListNode struct {
	key, value int
	pre, next *TwoListNode
}
// LRU结构
type LRUCache struct {
	m map[int]*TwoListNode
	cap int
	head, tail *TwoListNode
}

// 构造函数
func Constructor(cap int) *LRUCache {
	head := &TwoListNode{key:   0, value: 0, pre:   nil, next:  nil}
	tail := &TwoListNode{key:   0, value: 0, pre:   nil, next:  nil}
	head.next = tail
	tail.pre = head
	return &LRUCache{
		m:    make(map[int]*TwoListNode, cap),
		cap:  cap,
		head: head,
		tail: tail,
	}
}
// 在队头添加一个节点
func (this *LRUCache)AddNode(node *TwoListNode)  {
	head := this.head
	node.next = head.next
	node.next.pre = node
	node.pre = head
	head.next = node
}
// 删除一个节点
func (this *LRUCache)DeleteNode(node *TwoListNode) {
	node.pre.next = node.next
	node.next.pre = node.pre
}
// 把元素移动到头部
func (this *LRUCache)MoveToHead(node *TwoListNode) {
	// 先删除节点
	this.DeleteNode(node)
	// 再把节点添加到头部
	this.AddNode(node)
}

/*
GET操作
 */
// 如果有，将这个元素移动到首位置，返回值
// 如果没有，返回-1
func (this *LRUCache)Get(key int) int {
	if value, ok := this.m[key]; ok {
		// 移动到头部
		this.MoveToHead(this.m[key])
		return value.value
	}else {
		return -1
	}
}
// 如果元素存在，将其移动到最前面，并更新值
// 如果元素不存在，插入到元素首，放入map（判断容量）
func (this *LRUCache) Put(key int, value int) {
	tail := this.tail
	cache := this.m
	if v, exist := cache[key]; exist {
		v.value = value
		this.MoveToHead(v)
	} else {
		v := &TwoListNode{key, value, nil, nil}
		if len(this.m) == this.cap {
			delete(cache, tail.pre.key)
			this.DeleteNode(tail.pre)
		}
		this.AddNode(v)
		cache[key] = v
	}
}

func (l *LRUCache)getCache(){
	for n := l.head; n != nil; n = n.next{
		fmt.Println(n.key, n.value)
	}
}



func main() {
	lru := Constructor(3)
	lru.Put(11,1)
	lru.Put(22,2)
	lru.Put(33,3)
	lru.Put(44,4)

	lru.getCache()
	fmt.Println("-------------------------")

	v := lru.Get(33)
	fmt.Println(v)

	fmt.Println("----------------------")
	lru.getCache()
}
